<!--
 * @Description: 
 * @Author: xiongkuobiao
 * @Date: 2023-02-02 11:02:52
 * @LastEditors: xiongkuobiao
 * @LastEditTime: 2023-04-10 11:20:06
-->
<!--
 * @Description: 
 * @Author: xiongkuobiao
 * @Date: 2023-02-02 11:02:52
 * @LastEditors: xiongkuobiao
 * @LastEditTime: 2023-02-02 12:19:43
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
</head>

<body></body>
<script>
    // 用`双端指针`的方式，将三数之和转化为两数之和
    let nums = [1, 1, 2, 3, 4, 5, 6];
    let target = 8;
    // function findThree(arr, target) {
    //   // 先将数组从小到大排序
    //   arr.sort((a, b) => a - b);
    //   let result = [];
    //   for (let i = 0; i < arr.length; i++) {
    //     // 跳过重复的arr[i]值, 比如[2, 1, 1],跳过第二个1
    //     if (i && arr[i] === arr[i - 1]) continue;
    //     let left = i + 1;
    //     let right = arr.length - 1;

    //     // 双端指针left、right
    //     while (left < right) {
    //       let sum = arr[i] + arr[left] + arr[right];
    //       if (sum > target) {
    //         right--;
    //       } else if (sum < target) {
    //         left++;
    //       } else {
    //         // 先取arr[left]，然后left++, 两步合成一步；arr[right--]同样的逻辑
    //         result.push([arr[i], arr[left++], arr[right--]]);
    //         while (arr[left] === arr[left - 1]) {
    //           // 跳过重复的arr[left]值,
    //           left++;
    //         }
    //         while (arr[right] === arr[right + 1]) {
    //           // 跳过重复的arr[right]值
    //           right--;
    //         }
    //       }
    //     }
    //   }
    //   return result;
    // }
    function findThree(arr, target) {
        arr.sort((a, b) => a - b);
        let result = [];
        for (let i = 0; i < arr.length; i++) {
            if (i && arr[i] === arr[i - 1]) continue;
            let left = i + 1;
            let right = arr.length - 1;
            while (right > left) {
                let sum = arr[i] + arr[left] + arr[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    result.push([arr[i], arr[left++], arr[right--]]);
                    while (arr[left] == arr[left + 1]) {
                        left++;
                    }
                    while (arr[right] == arr[right - 1]) {
                        right--;
                    }
                }
            }
        }
        return result;
    }
    console.log(findThree(nums, target));
</script>

</html>